package 中等.搜索.广度优先搜索;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个正整数 n ，你可以做如下操作：
 * <p>
 * 如果 n 是偶数，则用 n / 2替换 n 。
 * 如果 n 是奇数，则可以用 n + 1或n - 1替换 n 。
 * n 变为 1 所需的最小替换次数是多少？
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/integer-replacement
 */
public class 整数替换_397 {

    private static Map<Long, Integer> map = new HashMap<>();

    public static void main(String[] args) {

        System.out.println(dfsIntegerReplacement(7));

    }

    /**
     * 相当于一颗树结构，n为树的根节点，
     * 偶数的子节点为n/2，奇数的子节点为n-1和n+1
     * <p>
     * 广度优先搜索
     *
     * @param n
     * @return
     */
    public static int integerReplacement(int n) {
        //int的最小值要比最大值得绝对值多1，防止cur+1，cur-1越界
        n = n * -1;
        //n的下一层开始算
        int count = -1;
        Deque<Integer> deque = new ArrayDeque<>();
        deque.addLast(n);
        while (!deque.isEmpty()) {
            int size = deque.size();
            //一层
            count++;
            while (size-- > 0) {
                Integer cur = deque.pollFirst();
                //当前层出现了1，返回层数
                if (cur == -1) {
                    return count;
                }
                if (cur % 2 == 0) {
                    deque.addLast(cur / 2);
                } else {
                    deque.addLast(cur + 1);
                    deque.addLast(cur - 1);
                }
            }
        }
        return count;
    }

    /**
     * 深度搜索+递归
     *
     * @param n
     * @return
     */
    public static int dfsIntegerReplacement(int n) {
        return dfsMemoFind(n);
    }

    public static int dfsFind(long n) {
        //停止条件
        if (n == 1) {
            return 0;
        }
        return n % 2 == 0 ? dfsFind(n / 2) + 1 : Math.min(dfsFind((n + 1) / 2), dfsFind((n - 1) / 2)) + 2;
    }

    /**
     * 记忆化搜索
     * 5->6，4->3,2
     * 5/2=2，5/2+1=3
     * 7->4，3
     * 7/2=3，7/2+1=4
     *
     * @param n
     * @return
     */
    public static int dfsMemoFind(long n) {
        if (map.containsKey(n)) {
            return map.get(n);
        }
        if (n == 1) {
            return 0;
        }
        if (n % 2 == 0) {
            int cur = dfsMemoFind(n / 2) + 1;
            map.put(n, cur);
            return cur;
        } else {
            int cur = Math.min(dfsMemoFind(n / 2), dfsMemoFind(n / 2 + 1)) + 2;
            map.put(n, cur);
            return cur;
        }
    }

}
